NPCAPC 2024 A

解き方

あと、yukicoder でジョルダン標準形を使う問題を作っても良いかも、200 マスのすごろく、0もあるサイコロ、ゴールする確率、10^{4} このターン数に対して

やはり、T なしで一個にして

マスの数を1000 くらいにしても良いかも

講義固有ベクトルを

広義

広義固有ベクトルを求めるところと、逆行列を求めるところがきついかもしれないけれど

前者は規則的っぽいし、校舎は

後者は一番右の列だけ求めれば良いと思うと$O(N^{2})$ でなんとか行けそうかな

$ O(N^{2})

yukicoder みたら、タイトルだけ決めて、何も変えていない問題合った…

合った ← あった

タイトルが"Like GTP" であることから

タイトルもよくわからんし、3月頃のノートをみてもこれに関するメモが見つからないし

なんのことかわからんかったけれど

しばらく考えて、

しばらくタイトルのGTP が何かを考えて、ようやくわかった、ゲーム論的確率論かな

確かにゲーム論的確率論を題材にした問題を考えた覚えはある

あいてが、あるノードを無限回訪れてはいけないという成約のもと動くとき、どれだけ稼げるか

正確には、あるN があって、それまでにそれ以上稼げるとか

そんな感じやったと思うけれど、何もメモ残していなかったっけ…

何となくどんな問題か覚えてはいるけれど、記憶は曖昧やし、なんかメモがないと再現は難しいかな

計算方法を色々考えて、あーだこーだできるできないって悩んでいた気もするし、なんか残っていると思っていたけれど

名前も考えたはず S がなんとかさんで、

ara

改めてノートを見返してみたけれど、やっぱりないかな…

結局、どうしたんやっけ

どれだけでも大きくできるかの判断は簡単やし証明もできるけれど

確率を求めてそれの逆数を答えにするのは

証明もはっきりとはできないし、そもそも計算できるのかも悩んで、けっきょくできたのかできなかったのか

NPCAPC A のscrapbox も書き進めたい 忘れないうちに

2つの文字列を考えると、長さの積の次元になってしまうから、文字列を1つにしたい

N=12 の場合のありうる文字列それぞれについて考えれば、文字列を1つずつ考えられる

kore

これは、文字列

これは、もともとの49次元の話における、どの状態を通る場合か、ということを考えるのと同じ

排他的に、一意になるようにするため、貪欲にとった時にそうなる場合をかんがえる

時←とき かんがえる←考える

2つのとり方がある長さ13文字の文字列を例に出して、どちらをとるかを書く

yukicoder の問題のメモもあるから、問題がある程度形になった後に、解説クォ

解説を書き始める

以下はたぶんGTP の問題のメモ

DAG なら簡単だということを解説に書く

下限である、または上限であることが言えれば、解説の中で説明できるかも、イテレーション

gaito

該当のSCC にn steps 以内に到達する確率で、

該当のSCC にn steps 以内に到達するbaai、

場合だけを考えたときに稼げる金額を考えて…

i

いや、単調にならないから、だめかな

やっぱり確率の逆数って言ってしまう解説じゃないとだめかな

到達するまでに稼げる金額とすれば有限帳の

有限長の列の

有限帳の列

有限長の列だけを考えて説明できるから、根源自称それぞれに

根元事象それぞれにお金をかけるって説明でいけるね

解説に、タイトルから察せられる通りGTP から〜って書く

n steps 以内に到達する場合だけを考えて稼げる金額って考え方

到達できない場合を無限大ってすれば、単調減少にはできるかな…だからなんだってはなしやけれど

tokoro

ところで稼げる金額の上限を求めさせようと思ったが、それだと誤差が厳しいし、やはりその逆数を求めさせることになりそう

そうすると、確率そのものになる

上限が無限大の場合は0 とする

以上、本日（2024/7/5）のメモ

ジョルダン標準形とは、行列の対角化を一般化したものであり、これも累乗が計算しやすい形となっています。

また、対角化とは違い、より広い範囲の行列に適用できる技術であるため、今回の問題にもそのまま活用できます。

下記の提出で、上で述べた次数$13$ の行列の場合について、実際にジョルダン標準形を使って答えを求めてみました。

しかし、ナイーブに考えると、行列の次数が$49$ となり、行列の積

しかし、ナイーブに考えると、行列の次数が$49$ となり、行列の積の計算がネックとなってしまいます。

ここでは、この問題特有の方法である行列の次元を小さくする方法と、一般的な行列の累乗の計算方法であるジョルダン標準形について紹介します。

しかし、ナイーブに考えると、行列の次数が$49$ となり、行列の積の計算がネックとなってしまいます。

ここでは、この問題特有の方法である行列の次元を小さくする方法と、一般的な行列の累乗の計算方法であるジョルダン標準形について紹介します。

下記の提出例をみる限り、この方法でのこれだけの工夫でも、実行時間制限内に計算することができると思われます。

しかし、ナイーブに考えると、行列の次数が$49$ となり、行列の積の計算がネックとなってしまいます。

ここでは、この問題特有の方法である行列の次元を小さくする方法と、一般的な行列の累乗の計算方法であるジョルダン標準形について紹介します。

下記の提出例をみる限り、この方法でのこれだけの工夫でも、実行時間制限内に計算することができると思われます。

しかし、ナイーブに考えると、行列の次数が$49$ となり、行列の積の計算がネックとなってしまいます。

ここでは、この問題特有の方法である行列の次元を小さくする方法と、一般的な行列の累乗の計算方法であるジョルダン標準形について紹介します。

下記の提出例をみる限り、この方法でのこれだけの工夫でも、実行時間制限内に計算することができると思われます。

しかし、ナイーブに考えると、行列の次数が$49$ となり、行列の積の計算がネックとなってしまいます。

ここでは、この問題特有の方法である行列の次元を小さくする方法と、一般的な行列の累乗の計算方法であるジョルダン標準形について紹介します。

下記の提出例をみる限り、この方法でのこれだけの工夫でも、実行時間制限内に計算することができると思われます。

しかし、ナイーブに考えると、行列の次数が$49$ となり、行列の積の計算がネックとなってしまいます。

ここでは、この問題特有の方法である行列の次元を小さくする方法と、一般的な行列の累乗の計算方法であるジョルダン標準形について紹介します。

下記の提出例をみる限り、この方法でのこれだけの工夫でも、実行時間制限内に計算することができると思われます。

ここで、$N=12$ の答えが924

しかし、ナイーブに考えると、行列の次数が$49$ となり、行列の積の計算がネックとなってしまいます。

ここでは、この問題特有の方法である行列の次元を小さくする方法と、一般的な行列の累乗の計算方法であるジョルダン標準形について紹介します。

下記の提出例をみる限り、この方法でのこれだけの工夫でも、実行時間制限内に計算することができると思われます。

そこで、この$2$つの文字列を組み合わせた文字列を$1$つ固定することで、行列の次元を$13$にする、つまり文字列の長さの和のオーダーにすることを考えます。

$N=12$ のときの答えが$924$

しかし、ナイーブに考えると、行列の次数が$49$ となり、行列の積の計算がネックとなってしまいます。

ここでは、この問題特有の方法である行列の次元を小さくする方法と、一般的な行列の累乗の計算方法であるジョルダン標準形について紹介します。

下記の提出例をみる限り、この方法でのこれだけの工夫でも、実行時間制限内に計算することができると思われます。

そこで、この$2$つの文字列を組み合わせた文字列を$1$つ固定することで、行列の次元を$13$にする、つまり文字列の長さの和のオーダーにすることを考えます。

$N=12$ のときの答えが$924$ であることから、このような文字列が$924$ 個あることがわかりますが、それらを一つ一つ処理していたら寧ろ効率が悪くなるため、同じ行列になるような文字列をまとめることで、$6$ つのグループに分けます。

具体的には、$1 \le k \le 6$ を満たす整数$k$ それぞれについて、体格

しかし、ナイーブに考えると、行列の次数が$49$ となり、行列の積の計算がネックとなってしまいます。

ここでは、この問題特有の方法である行列の次元を小さくする方法と、一般的な行列の累乗の計算方法であるジョルダン標準形について紹介します。

下記の提出例をみる限り、この方法でのこれだけの工夫でも、実行時間制限内に計算することができると思われます。

そこで、この$2$つの文字列を組み合わせた文字列を$1$つ固定することで、行列の次元を$13$にする、つまり文字列の長さの和のオーダーにすることを考えます。

$N=12$ のときの答えが$924$ であることから、このような文字列が$924$ 個あることがわかりますが、それらを一つ一つ処理していたら寧ろ効率が悪くなるため、同じ行列になるような文字列をまとめることで、$6$ つのグループに分けます。

具体的には、$0 \le k < 6$ を満たす整数$k$ それぞれについて、対角成分に$50$ が$6+k$ 個、$51$ が$6-k$ 個、$52$ が$1$ 個並び、そこから一つずれて$1$ が斜めに並ぶような行列になるグループが考えられます。

これにより行列の次数が上と比較しても半分以下となるため、行列の積は単純に考えると$8$ 倍効率化されます。

よって、行列が$6$ つに増えても全体では$\frac{3}{4}$ 程度の計算で答えが求められる見込みです。

下記の提出例を見る限り、上の方法と比較して、実際に実行時間が短くなっています。

しかし、ナイーブに考えると、行列の次数が$49$ となり、行列の積の計算がネックとなってしまいます。

ここでは、この問題特有の方法である行列の次元を小さくする方法と、一般的な行列の累乗の計算方法であるジョルダン標準形について紹介します。

下記の提出例をみる限り、この方法でのこれだけの工夫でも、実行時間制限内に計算することができると思われます。

そこで、この$2$つの文字列を組み合わせた文字列を$1$つ固定することで、行列の次元を$13$にする、つまり文字列の長さの和のオーダーにすることを考えます。

$N=12$ のときの答えが$924$ であることから、このような文字列が$924$ 個あることがわかりますが、それらを一つ一つ処理していたら寧ろ効率が悪くなるため、同じ行列になるような文字列をまとめることで、$6$ つのグループに分けます。

具体的には、$0 \le k < 6$ を満たす整数$k$ それぞれについて、対角成分に$50$ が$6+k$ 個、$51$ が$6-k$ 個、$52$ が$1$ 個並び、そこから一つずれて$1$ が斜めに並ぶような行列になるグループが考えられます。

これにより行列の次数が上と比較しても半分以下となるため、行列の積は単純に考えると$8$ 倍効率化されます。

よって、行列が$6$ つに増えても全体では$\frac{3}{4}$ 程度の計算で答えが求められる見込みです。

下記の提出例を見る限り、上の方法と比較して、実際に実行時間が短くなっています。

対角行列の積は簡単に求められるため、行列の対角化は行列の累乗を計算したいときの常套手段の一つと考えられます。

ただし、行列の対角化は任意の製法行列に対して可能

しかし、ナイーブに考えると、行列の次数が$49$ となり、行列の積の計算がネックとなってしまいます。

ここでは、この問題特有の方法である行列の次元を小さくする方法と、一般的な行列の累乗の計算方法であるジョルダン標準形について紹介します。

下記の提出例をみる限り、この方法でのこれだけの工夫でも、実行時間制限内に計算することができると思われます。

そこで、この$2$つの文字列を組み合わせた文字列を$1$つ固定することで、行列の次元を$13$にする、つまり文字列の長さの和のオーダーにすることを考えます。

$N=12$ のときの答えが$924$ であることから、このような文字列が$924$ 個あることがわかりますが、それらを一つ一つ処理していたら寧ろ効率が悪くなるため、同じ行列になるような文字列をまとめることで、$6$ つのグループに分けます。

具体的には、$0 \le k < 6$ を満たす整数$k$ それぞれについて、対角成分に$50$ が$6+k$ 個、$51$ が$6-k$ 個、$52$ が$1$ 個並び、そこから一つずれて$1$ が斜めに並ぶような行列になるグループが考えられます。

これにより行列の次数が上と比較しても半分以下となるため、行列の積は単純に考えると$8$ 倍効率化されます。

よって、行列が$6$ つに増えても全体では$\frac{3}{4}$ 程度の計算で答えが求められる見込みです。

下記の提出例を見る限り、上の方法と比較して、実際に実行時間が短くなっています。

対角行列の積は簡単に求められるため、行列の対角化は行列の累乗を計算したいときの常套手段の一つと考えられます。

ただし、行列の対角化は任意の正方行列に対して可能というわけではなく、今回の問題に対しても上で考えた行列を対角化することはできません。

しかし、ナイーブに考えると、行列の次数が$49$ となり、行列の積の計算がネックとなってしまいます。

ここでは、この問題特有の方法である行列の次元を小さくする方法と、一般的な行列の累乗の計算方法であるジョルダン標準形について紹介します。

下記の提出例をみる限り、この方法でのこれだけの工夫でも、実行時間制限内に計算することができると思われます。

そこで、この$2$つの文字列を組み合わせた文字列を$1$つ固定することで、行列の次元を$13$にする、つまり文字列の長さの和のオーダーにすることを考えます。

$N=12$ のときの答えが$924$ であることから、このような文字列が$924$ 個あることがわかりますが、それらを一つ一つ処理していたら寧ろ効率が悪くなるため、同じ行列になるような文字列をまとめることで、$6$ つのグループに分けます。

具体的には、$0 \le k < 6$ を満たす整数$k$ それぞれについて、対角成分に$50$ が$6+k$ 個、$51$ が$6-k$ 個、$52$ が$1$ 個並び、そこから一つずれて$1$ が斜めに並ぶような行列になるグループが考えられます。

これにより行列の次数が上と比較しても半分以下となるため、行列の積は単純に考えると$8$ 倍効率化されます。

よって、行列が$6$ つに増えても全体では$\frac{3}{4}$ 程度の計算で答えが求められる見込みです。

下記の提出例を見る限り、上の方法と比較して、実際に実行時間が短くなっています。

対角行列の積は簡単に求められるため、行列の対角化は行列の累乗を計算したいときの常套手段の一つと考えられます。

ただし、行列の対角化は任意の正方行列に対して可能というわけではなく、今回の問題に対しても上で考えた行列を対角化することはできません。

そのため、今回の問題では対角化による行列の累乗の計算を活用することは難しいと思われます。

ジョルダン標準形とは、行列の体格可を

しかし、ナイーブに考えると、行列の次数が$49$ となり、行列の積の計算がネックとなってしまいます。

ここでは、この問題特有の方法である行列の次元を小さくする方法と、一般的な行列の累乗の計算方法であるジョルダン標準形について紹介します。

下記の提出例をみる限り、この方法でのこれだけの工夫でも、実行時間制限内に計算することができると思われます。

そこで、この$2$つの文字列を組み合わせた文字列を$1$つ固定することで、行列の次元を$13$にする、つまり文字列の長さの和のオーダーにすることを考えます。

$N=12$ のときの答えが$924$ であることから、このような文字列が$924$ 個あることがわかりますが、それらを一つ一つ処理していたら寧ろ効率が悪くなるため、同じ行列になるような文字列をまとめることで、$6$ つのグループに分けます。

具体的には、$0 \le k < 6$ を満たす整数$k$ それぞれについて、対角成分に$50$ が$6+k$ 個、$51$ が$6-k$ 個、$52$ が$1$ 個並び、そこから一つずれて$1$ が斜めに並ぶような行列になるグループが考えられます。

これにより行列の次数が上と比較しても半分以下となるため、行列の積は単純に考えると$8$ 倍効率化されます。

よって、行列が$6$ つに増えても全体では$\frac{3}{4}$ 程度の計算で答えが求められる見込みです。

下記の提出例を見る限り、上の方法と比較して、実際に実行時間が短くなっています。

対角行列の積は簡単に求められるため、行列の対角化は行列の累乗を計算したいときの常套手段の一つと考えられます。

ただし、行列の対角化は任意の正方行列に対して可能というわけではなく、今回の問題に対しても上で考えた行列を対角化することはできません。

そのため、今回の問題では対角化による行列の累乗の計算を活用することは難しいと思われます。

ジョルダン標準形とは、行列の対角可を一般化したものであり、これも累乗が計算しやすい形となっています。

また、対格かとは

しかし、ナイーブに考えると、行列の次数が$49$ となり、行列の積の計算がネックとなってしまいます。

ここでは、この問題特有の方法である行列の次元を小さくする方法と、一般的な行列の累乗の計算方法であるジョルダン標準形について紹介します。

下記の提出例をみる限り、この方法でのこれだけの工夫でも、実行時間制限内に計算することができると思われます。

そこで、この$2$つの文字列を組み合わせた文字列を$1$つ固定することで、行列の次元を$13$にする、つまり文字列の長さの和のオーダーにすることを考えます。

$N=12$ のときの答えが$924$ であることから、このような文字列が$924$ 個あることがわかりますが、それらを一つ一つ処理していたら寧ろ効率が悪くなるため、同じ行列になるような文字列をまとめることで、$6$ つのグループに分けます。

具体的には、$0 \le k < 6$ を満たす整数$k$ それぞれについて、対角成分に$50$ が$6+k$ 個、$51$ が$6-k$ 個、$52$ が$1$ 個並び、そこから一つずれて$1$ が斜めに並ぶような行列になるグループが考えられます。

これにより行列の次数が上と比較しても半分以下となるため、行列の積は単純に考えると$8$ 倍効率化されます。

よって、行列が$6$ つに増えても全体では$\frac{3}{4}$ 程度の計算で答えが求められる見込みです。

下記の提出例を見る限り、上の方法と比較して、実際に実行時間が短くなっています。

対角行列の積は簡単に求められるため、行列の対角化は行列の累乗を計算したいときの常套手段の一つと考えられます。

ただし、行列の対角化は任意の正方行列に対して可能というわけではなく、今回の問題に対しても上で考えた行列を対角化することはできません。

そのため、今回の問題では対角化による行列の累乗の計算を活用することは難しいと思われます。

ジョルダン標準形とは、行列の対角化を一般化したものであり、これも累乗が計算しやすい形となっています。

また、対角化とは違い、より広い範囲の行列に適用できる技術であるため、今回の問題にもそのまま活用できます。

下記の提出で、上で述べた次数$13$ の行列の場合について、実際にジョルダン標準形を使って答えを求めてみました。

ちなみに今回の問題でジョルダン標準形が使えた理由としては、上で考えた行列が三角行列であったことが理由として大きいと考えます。

三角行列であることによって、計算を別途しなくとも固有値がわかり、固有値が$\mathbb{F}_{998244353}$ の元であることが明確であるからです。

三角行列

補集合 を考えて、包除原理を使う方法でも解けそう…

補集合とか包除原理とか考えてはいたのに思いつかなかった…こっちの方が簡単そう

できたから解説を書いておくかな

$N<12$ のときの答えは明らかに$0$ であるため、$N \ge 12$ のときのみ考えます。

全体集合$U$ を「英大文字および英小文字だけからなる長さ$N$ の文字列全体の集合」としたときの補集合$C$ を考えると、答えは$|U|-|C|$ と表すことができます。

$N<12$ のときの答えは明らかに$0$ であるため、$N \ge 12$ のときのみ考えます。

全体集合$U$ を「英大文字および英小文字だけからなる長さ$N$ の文字列全体の集合」としたときの補集合$C$ を考えると、答えは$|U|-|C|$ と表すことができます。

このとき$C = A \cup B$ であるため、$|C| = |A| + |B| - |A \cap B|$ となります。

$N<12$ のときの答えは明らかに$0$ であるため、$N \ge 12$ のときのみ考えます。

全体集合$U$ を「英大文字および英小文字だけからなる長さ$N$ の文字列全体の集合」としたときの補集合$C$ を考えると、答えは$|U|-|C|$ と表すことができます。

このとき$C = A \cup B$ であるため、$|C| = |A| + |B| - |A \cap B|$ となります。

まず$|A|$ について考えます。

よって、$A$ の個数は以下の式によって計算できます。

$$|A| = \sum_{k = 0}$$

$N<12$ のときの答えは明らかに$0$ であるため、$N \ge 12$ のときのみ考えます。

全体集合$U$ を「英大文字および英小文字だけからなる長さ$N$ の文字列全体の集合」としたときの補集合$C$ を考えると、答えは$|U|-|C|$ と表すことができます。

このとき$C = A \cup B$ であるため、$|C| = |A| + |B| - |A \cap B|$ となります。

まず$|A|$ について考えます。

よって、$A$ の個数は以下の式によって計算できます。

$\displaystyle |A| = \sum_{k = 0}^{5} \left( 51^{n-k} \times _{n} \mathrm{C}_{k} \right)$

また、大文字と小文字を入れ替える変換を考えると、$A$ と$B$ は1対1 に対応するため、$|B| = |A|$ であることがわかります。

最後に$|A \cap B|$ について考えます。

$N<12$ のときの答えは明らかに$0$ であるため、$N \ge 12$ のときのみ考えます。

全体集合$U$ を「英大文字および英小文字だけからなる長さ$N$ の文字列全体の集合」としたときの補集合$C$ を考えると、答えは$|U|-|C|$ と表すことができます。

このとき$C = A \cup B$ であるため、$|C| = |A| + |B| - |A \cap B|$ となります。

まず$|A|$ について考えます。

よって、$A$ の個数は以下の式によって計算できます。

$\displaystyle |A| = \sum_{k = 0}^{5} \left( 51^{n-k} \times _{n} \mathrm{C}_{k} \right)$

また、大文字と小文字を入れ替える変換を考えると、$A$ と$B$ は1対1 に対応するため、$|B| = |A|$ であることがわかります。

最後に$|A \cap B|$ について考えます。

よって、$A \cap B$ の個数は以下の式によって計算できます。

$\displaystyle |A \cap B| = \sum_{k = 0}^{5} \sum_{l = 0}^{5} \left( 50^{n-k-l} \times _{n} \mathrm{C}_{k+l} \times {}_{k+l} \mathrm{C}_{k} \right)$

以上により、答えを求めることができます。

$N<12$ のときの答えは明らかに$0$ であるため、$N \ge 12$ のときのみ考えます。

全体集合$U$ を「英大文字および英小文字だけからなる長さ$N$ の文字列全体の集合」としたときの補集合$C$ を考えると、答えは$|U|-|C|$ と表すことができます。

このとき$C = A \cup B$ であるため、$|C| = |A| + |B| - |A \cap B|$ となります。

まず$|A|$ について考えます。

よって、$A$ の個数は以下の式によって計算できます。

$\displaystyle |A| = \sum_{k = 0}^{5} \left( 51^{n-k} \times _{n} \mathrm{C}_{k} \right)$

また、大文字と小文字を入れ替える変換を考えると、$A$ と$B$ は1対1 に対応するため、$|B| = |A|$ であることがわかります。

最後に$|A \cap B|$ について考えます。

よって、$A \cap B$ の個数は以下の式によって計算できます。

$\displaystyle |A \cap B| = \sum_{k = 0}^{5} \sum_{l = 0}^{5} \left( 50^{n-k-l} \times _{n} \mathrm{C}_{k+l} \times {}_{k+l} \mathrm{C}_{k} \right)$

以上により、答えを求めることができます。

$N<12$ のときの答えは明らかに$0$ であるため、$N \ge 12$ のときのみ考えます。

全体集合$U$ を「英大文字および英小文字だけからなる長さ$N$ の文字列全体の集合」としたときの補集合$C$ を考えると、答えは$|U|-|C|$ と表すことができます。

このとき$C = A \cup B$ であるため、$|C| = |A| + |B| - |A \cap B|$ となります。

まず$|A|$ について考えます。

よって、$A$ の個数は以下の式によって計算できます。

$\displaystyle |A| = \sum_{k = 0}^{5} \left( 51^{n-k} \times _{n} \mathrm{C}_{k} \right)$

また、大文字と小文字を入れ替える変換を考えると、$A$ と$B$ は1対1 に対応するため、$|B| = |A|$ であることがわかります。

最後に$|A \cap B|$ について考えます。

よって、$A \cap B$ の個数は以下の式によって計算できます。

$\displaystyle |A \cap B| = \sum_{k = 0}^{5} \sum_{l = 0}^{5} \left( 50^{n-k-l} \times _{n} \mathrm{C}_{k+l} \times {}_{k+l} \mathrm{C}_{k} \right)$

以上により、答えを求めることができます。

$N<12$ のときの答えは明らかに$0$ であるため、$N \ge 12$ のときのみ考えます。

全体集合$U$ を「英大文字および英小文字だけからなる長さ$N$ の文字列全体の集合」としたときの補集合$C$ を考えると、答えは$|U|-|C|$ と表すことができます。

このとき$C = A \cup B$ であるため、$|C| = |A| + |B| - |A \cap B|$ となります。

まず$|A|$ について考えます。

よって、$A$ の個数は以下の式によって計算できます。

$\displaystyle |A| = \sum_{k = 0}^{5} \left( 51^{n-k} \times _{n} \mathrm{C}_{k} \right)$

また、大文字と小文字を入れ替える変換を考えると、$A$ と$B$ は1対1 に対応するため、$|B| = |A|$ であることがわかります。

最後に$|A \cap B|$ について考えます。

よって、$A \cap B$ の個数は以下の式によって計算できます。

$\displaystyle |A \cap B| = \sum_{k = 0}^{5} \sum_{l = 0}^{5} \left( 50^{n-k-l} \times _{n} \mathrm{C}_{k+l} \times {}_{k+l} \mathrm{C}_{k} \right)$

以上により、答えを求めることができます。

しかし、ナイーブに考えると、行列の次数が$49$ となり、行列の積の計算がネックとなってしまいます。

ここでは、この問題特有の方法である行列の次元を小さくする方法と、一般的な行列の累乗の計算方法であるジョルダン標準形について紹介します。

下記の提出例をみる限り、この方法でのこれだけの工夫でも、実行時間制限内に計算することができると思われます。

$N=12$ のときの答えが$924$であることから、

しかし、ナイーブに考えると、行列の次数が$49$ となり、行列の積の計算がネックとなってしまいます。

ここでは、この問題特有の方法である行列の次元を小さくする方法と、一般的な行列の累乗の計算方法であるジョルダン標準形について紹介します。

下記の提出例をみる限り、この方法でのこれだけの工夫でも、実行時間制限内に計算することができると思われます。

ここで、$N=12$ の答えが924

タイトルは !補集合を考える方法